package com.shuang.tree10;

import java.util.*;

public class LevelOrder {
    //层序遍历 利用队列实现
    public List<List<Integer>> levelOrder(TreeNode root) {

        //用于封装结果的集合
        List<List<Integer>> resList = new ArrayList<>();

        if (root == null) {
            return resList;
        }

        //定义一个队列
        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            //用于封装每层结果的集合
            List<Integer> list = new ArrayList<>();

            //用于记录当前层需要封装的结果个数
            int len = queue.size();

            while (len > 0) {
                //弹出一个节点
                TreeNode node = queue.poll();
                //加到这层集合中
                list.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }

                //弹出一个节点 这一层要封装的结果个数减一
                len--;
            }

            //将这一层结果加到最终结果集合中
            resList.add(list);

        }

        return resList;

    }
}
